package com.algorithm.dp;

import java.util.Arrays;

public class NumArray {

    boolean flag = false;
    int[] mem ;

    public static void main(String[] args) {
        int i = new NumArray(new int[]{1}).climbStairs(44);
        System.out.println(i);
        //NumArray numArray = new NumArray(new int[]{-2,0,3,-5,2,-1});
        //numArray.makeDp();

    }

    /**
     * 爬楼梯种类计数
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int res = 0;
        if (n == 0 || n==1){
            return 1;
        }else{
            if (!flag){
                flag = true;
                mem = new int[n+1];
            }
            int l;
            if (mem[n-1] == 0){
                l = climbStairs(n - 1);
            }else {
                l = mem[n-1];
            }
            int ll;
            if (mem[n-2] == 0) {
                ll = climbStairs(n - 2);
            }else {
                ll = mem[n-2];
            }
            res = l + ll;
            mem[n] = res;
        }
        return res;
    }

    int[] dp;
    int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;

        makeDp();
    }

    void makeDp(){
        if (nums.length == 0) return;
        int length = nums.length;
        dp = new int[length];
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i] = dp[i-1] + nums[i];
        }

    }

    /**
     * 查找子数组和
     * @param i
     * @param j
     * @return
     */
    public int sumRange(int i, int j) {
        if (i == 0){
            return dp[j];
        }else {
            return dp[j] - dp[i -1];
        }
    }
}
